﻿<HTML>

<HEAD>
  <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=utf-8" />  
  <TITLE>HeO</TITLE>
  <LINK HREF="doc.css" REL=STYLESHEET>
</HEAD>


<BODY>


<!-- ============================================ -->


  <H1>HeO</H1>

  <A HREF="../index.html">[Previous]</A><A HREF="solvers.html">[Next]</A><A HREF="../index.html">[Home]</A>

  <H2>Contents</H2>

  <UL>
    <LI><A HREF="#intro">Introduction</A></LI> 
    <LI><A HREF="#sysreq">System Requirements</A></LI> 
    <LI><A HREF="#install">Installation and Directory Structure</A></LI> 
    <LI><A HREF="#archit">Understanding HeO Acrchitecture</A></LI> 
  </UL>


<!-- ============================================ -->


  <A NAME="intro"></A>
  <H3>Introduction</H3>

  <P>
    <B>HeO</B> (<B>He</B>uristic <B>O</B>ptimization) is a cross-platform library that provides various parallel metaheuristic algorithms for hard combinatorial optimization problems. 
    The library is written in C++ using modern programming, metaprogramming and parallel computing techniques. 
    The main goal of the project is to provide the researchers with the state-of-the-art and easy-to-use software tool that can be applied to a wide range of combinatorial optimization problems.
  </P> 

  <P>
    <B>Key features</B>
  </P>  

   <UL>
    <LI>The source code is platform-independent and can be used on Windows and Linux systems without any alterations.</LI>
    <LI>x86 and x64 architectures are supported.</LI>
    <LI>All optimization methods are implemented as algorithmic skeletons that can be applied to different optimization problems.</LI>
    <LI>Each optimization method is implemented using two parallel programming techniques: OpenMP and MPI.</LI> 
    <LI>The MPI versions of the optimization methods use the original MPI wrapper compatible with MPICH and LAM libraries.</LI>
    <LI>Parallelism is transparent to the library users.</LI>
    <LI>The original reflection technology allows loading, saving, printing and passing instances in a uniform way.</LI>
    <LI>The original memory manager speeds up dynamic memory operations.</LI>
    <LI>Wizards ease the process of creating user projects.</LI>
  </UL>


<!-- ============================================ -->


  <A NAME="sysreq"></A>
  <H3>System Requirements</H3>

  <P>
    To build and run projects that use the HeO library you need to have installed: 
  </P>  

  <UL>
    <LI>MS VC++ (2005 or higher), GCC with OpenMP support (4.1.2 or higher) or Intel C++ Compiler (11.1 or higher) depending on your system.</LI>
    <LI>MPI-1 or MPI-2 library (e.g., MPICH or LAM).</LI>
    <LI>Platform SDK for Windows.</LI>
  </UL>

<!-- ============================================ -->


  <A NAME="install"></A>
  <H3>Installation and Directory Structure</H3>

  <P>
    To install the HeO library you have to perform the following steps:
  </P>  

  <OL>
    <LI>Download the appropriate source file.</LI>
    <LI>Unpack the downloaded source file into any desired folder.</LI>
    <LI>Change to the root folder of the library (<TT CLASS="folder">/heo</TT>).</LI>
  </OL>    
  
  <P>
    A brief (yet not complete) description of the HeO directory structure is given in the table below.
  </P>

    <TABLE>
      <TBODY>

        <TR>
          <TH COLSPAN="3">HeO Directory Structure</TH>
        </TR>

        <TR>
          <TH>Name</TH>
          <TH>Type</TH>
          <TH>Description</TH>
        </TR>

        <TR>
          <TD CLASS="l0">/heo</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Root folder.</TD>
        </TR>


        <TR>
          <TD CLASS="l1">/contrib</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Contributed files and libraries that are not considered part of the HeO library.</TD>
        </TR>

        <TR>
          <TD CLASS="l1">/doc</TD>
          <TD ALIGN="center">folder</TD>
          <TD>HeO documentation.</TD>
        </TR>

        <TR>
          <TD CLASS="l1">/logins</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Files with logins and passwords (for MPI runs).</TD>
        </TR>



        <TR>
          <TD CLASS="l1">/problems</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Problem instances.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/generic</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Generic problem instances.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/maxsat</TD>
          <TD ALIGN="center">folder</TD>
          <TD>MAX-SAT problem instances.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/onemax</TD>
          <TD ALIGN="center">folder</TD>
          <TD>ONE-MAX problem instances.</TD>
        </TR>



        <TR>
          <TD CLASS="l1">/projects</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Sample and user projects.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/generic</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Sample generic projects.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/maxsat</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Sample MAX-SAT projects.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/onemax</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Sample ONE-MAX projects.</TD>
        </TR>



        <TR>
          <TD CLASS="l1">/solvers</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Source files for algorithm-specific classes.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/ga</TD>
          <TD ALIGN="center">folder</TD>
          <TD>GA source files.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/sa</TD>
          <TD ALIGN="center">folder</TD>
          <TD>SA source files.</TD>
        </TR>



        <TR>
          <TD CLASS="l1">/src</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Source files for auxillary classes and utilities.</TD>
        </TR>

        <TR>
          <TD CLASS="l1">/license.txt</TD>
          <TD ALIGN="center">file</TD>
          <TD>License agreement.</TD>
        </TR>

        <TR>
          <TD CLASS="l1">/readme.txt</TD>
          <TD ALIGN="center">file</TD>
          <TD>README file.</TD>
        </TR>

      </TBODY>
    </TABLE>
  
  <P>
  </P>

  
<!-- ============================================ -->


  <A NAME="archit"></A>
  <H3>Understanding HeO Architecture</H3>

  <P>
    The library is designed as a set of classes that can be divided into two large groups: 
  </P>

  <UL>
    <LI><B>Algorithm-specific classes</B>.</LI>
    <LI><B>Auxiliary classes</B>.</LI>
  </UL>

  <P>
    Algorithm-specific classes abstract the features specific to optimization methods. 
    Their source code is stored in the <TT CLASS="folder">/heo/solvers</TT> folder.
    Auxiliary classes perform different subsidiary functions.
    Their source code is stored in the <TT CLASS="folder">/heo/src</TT> folder.
  </P>

  <P>
    At present two optimizations methods are implemented: genetic algorithm (GA) and simulated annealing (SA).
  </P>

  <P>
    The core of the algorithm-specific classes are the so-called <B>solvers</B>. 
    Each solver is a class template that implements the particular optimization method using the particular parallel programming technique.
    This means that there are four solvers in the library (two for each optimization method).
  </P>

  <P>
    The name of each solver consists of the name of the optimization method and the abbreviation of the parallel programming technique with underscore between words.
    For example, <TT>GA_OMP</TT> means the solver that implements the OpenMP version of the genetic algorithm.
  </P>

  <P>
    The source code for the solvers that implement the same optimization method is contained in the folder <TT CLASS="folder">/heo/solvers/&lt;method&nbsp;name&gt;</TT> in the following files:
  </P>

  <UL>
    <LI><TT>&lt;method&nbsp;name&gt;_common.h &mdash;</TT> part of the source code common to both solvers.</LI>
    <LI><TT>&lt;method&nbsp;name&gt;_mpi.h &mdash;</TT> source code for the MPI solver.</LI>
    <LI><TT>&lt;method&nbsp;name&gt;_omp.h &mdash;</TT> source code for the OpenMP solver.</LI>
  </UL>

  <P>
     For example, the source code for both GA solvers is stored in the folder <TT CLASS="folder">/heo/solvers/ga</TT> in the files <TT>ga_common.h</TT>, <TT>ga_mpi.h</TT> and <TT>ga_omp.h</TT>.
  </P>

  <P>
    The behavior of the solvers for one and the same optimization method is controlled by the special configuration class. 
    This class has the name <TT>&lt;method&nbsp;name&gt;_Config</TT> (e.g., <TT>GA_Config</TT>).
    Its source code is stored in the same folder as for the solvers in the file <TT>&lt;method&nbsp;name&gt;_config.h</TT> (e.g., <TT>ga_config.h</TT>).
  </P>

  <P>
     Solvers of the HeO library are designed as <B>algorithmic skeletons</B>. 
     This means that each solver:
  </P>

  <UL>
    <LI>abstracts only algorithm-specific features regardless of any optimization problem; </LI>
    <LI>hides all aspects regarding parallelization.</LI>
  </UL>

  <P>
     This approach allows to apply each solver to a wide range of optimization problems and makes parallelism transparent to the library users.   
  </P>

  <P>
    All solvers are declared as class templates. 
    Solvers for one and the same optimization method are derived from one and the same parent class template.
    For example, <TT>GA_MPI</TT> and <TT>GA_OMP</TT> class templates are derived from the class template <TT>GA</TT>.  
    Below is the example of the <TT>GA_MPI</TT> class template declaration from the <TT>ga_mpi.h</TT>:
  </P>

  <DIV CLASS="code">
    template&lt;class P, class S, class C&gt;<BR>
    class GA_MPI:<BR>
    &nbsp;&nbsp;&nbsp;&nbsp;public GA&lt;P, S, C&gt;<BR>
    {<BR>
    &nbsp;...<BR>
    }<BR>
  </DIV>


  <P>
    To use any solver the user has to replace its template parameters <TT>P</TT>, <TT>S</TT>, and <TT>C</TT> with three classes. 
    The first two classes are <B>problem-specific</B> and have to be implemented by the user.
    They abstract the features of the problem and its admissible solutions respectively. 
    In order to have the ability to interact with the solver these classes must have necessary methods specific to optimization algorithm (e.g., crossover and mutation methods for GA).
    The third parameter is the class that inherits properties of the problem-specific configuration class (implemented by the user) and the algorithm-specific configuration class (implemented in the library).
    All user source files and projects are stored in the <TT CLASS="folder">/heo/projects</TT> folder.
  </P>


  <P>
    To apply the desired solver to the particular problem the user has to perform a number of standard operations: read command line parameters, configuration file and problem instance file, initialize and run solver, print the results, etc. 
    There are auxiliary classes that perform this routine.
    These class templates are called <TT>Run_MPI</TT> and <TT>Run_OMP</TT>.
    Below is the example of the <TT>Run_MPI</TT> class template declaration from the <TT>run_mpi.h</TT>:
  </P>

  <DIV CLASS="code">
    template&lt;class S&gt;<BR>
    class Run_MPI<BR>
    {<BR>
    &nbsp;...<BR>
    }</BR>
  </DIV>


  <P>
    To run MPI or OpenMP solver the user has to substitute it for <TT>S</TT> in the <TT>Run_MPI</TT> or <TT>Run_OMP</TT> class templates and call the <TT>run()</TT> method. 
  </P>

  <P>
    The UML diagram on the figure below demonstrates the relationships between these classes and class templates for the genetic algorithm solvers.
    Problem-specific classes are shown in green, solver-specific and auxiliary classes and templates are shown in red and yellow respectively.
  </P>

  <IMG SRC="../images/uml.png" WIDTH="800px"></IMG>

 <P>
  </P>

 
  <H2>&nbsp;</H2>

  <A HREF="../index.html">[Previous]</A><A HREF="solvers.html">[Next]</A><A HREF="../index.html">[Home]</A>


<!-- ============================================ -->


</BODY>

</HTML>


